import java.util.*;
/*
* MinStack最小栈
* */

class MinStack {

    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if(minStack.empty()) {
            minStack.push(val);
        }else {
            int peekNum = minStack.peek();
            if(val <= peekNum) {
                minStack.push(val);
            }
        }
    }

    public void pop() {
        int val = stack.pop();
        if(val == minStack.peek()) {
            minStack.pop();
        }
    }

    //peek
    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}
public class Mystack {

    public int[] elem;
    public int usedSize;

    public static final int DEFAULT_CAPACITY = 10;
    public Mystack() {
        this.elem = new int[DEFAULT_CAPACITY];
    }

    //压栈 入栈
    public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    //出栈
    public int pop() {
        if(isEmpty()) {
            throw new EmptyStackException("栈为空....");
        }
        int oldVal = elem[usedSize-1];
        usedSize--;
        //elem[usedSize] = null;
        return oldVal;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    public int peek() {
        if(isEmpty()) {
            throw new EmptyStackException("栈为空....");
        }
        return elem[usedSize-1];
    }

    public static void main(String[] args) {
            MyQueue myQueue = new MyQueue();
            myQueue.offer(1);
            myQueue.offer(2);
            myQueue.offer(3);
            myQueue.offer(4);

            System.out.println(myQueue.poll());
            System.out.println(myQueue.peek());

            Queue<Integer> queue = new LinkedList<>();

            //双端队列
            Deque<Integer> queue2 = new LinkedList<>();

            //双端队列
            Deque<Integer> queue3 = new ArrayDeque<>();

        }

        public boolean IsPopOrder (int[] pushA, int[] popA) {
            // write code here
            Stack<Integer> stack = new Stack<>();
            int j = 0;
            for (int i = 0; i < pushA.length; i++) {
                stack.push(pushA[i]);
                while (!stack.empty() && j < popA.length
                        && stack.peek() == popA[j]) {
                    stack.pop();
                    j++;
                }
            }
            //return j >= popA.length;
            return stack.empty();
        }

        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<>();
            //1. 遍历字符串
            for(int i = 0;i < s.length();i++) {
                char ch = s.charAt(i);
                //2.是不是左括号
                if(ch == '(' || ch == '[' || ch == '{') {
                    stack.push(ch);
                }else {
                    //3.右括号
                    //3.1 栈为空
                    if(stack.isEmpty()) {
                        return false;
                    }
                    //3.2 栈不为空
                    char ch2 = stack.peek();//左括号
                    if(ch == ')' && ch2 == '('  || ch == ']'
                            && ch2 == '[' || ch == '}' && ch2 == '{') {
                        stack.pop();
                    }else {
                        return false;
                    }
                }
            }
            //字符串遍历完了 栈还是不为空
            if(!stack.isEmpty()) {
                return false;
            }
            return true;
        }


        public int evalRPN(String[] tokens) {
            Stack<Integer> stack = new Stack<>();
            for(int i = 0;i < tokens.length;i++) {
                String str = tokens[i];
                if(!isOperations(str)) {
                    //不是运算符  说明是数字
                    int val = Integer.valueOf(str);
                    stack.push(val);
                }else {
                    //是运算符
                    int num2 = stack.pop();
                    int num1 = stack.pop();
                    switch(str) {
                        case "+":
                            stack.push(num1+num2);
                            break;
                        case "-":
                            stack.push(num1-num2);
                            break;
                        case "*":
                            stack.push(num1*num2);
                            break;
                        case "/":
                            stack.push(num1/num2);
                            break;
                    }
                }
            }

            return stack.pop();
        }
        /*判断当前字符串是不是一个运算符 */
        private boolean isOperations(String str) {
            if(str.equals("+") || str.equals("-") || str.equals("*") ||
                    str.equals("/")) {
                return true;
            }
            return false;
        }
        public static void main2(String[] args) {
            LinkedList<Integer> stack = new LinkedList<>();
            stack.push(1);
            stack.push(2);
            stack.push(3);

            System.out.println(stack.pop());

            System.out.println(stack.peek());

        }
        public static void main1(String[] args) {
            Mystack stack = new Mystack();
            stack.push(12);
            stack.push(23);
            stack.push(34);
            stack.push(45);

            //pop: 删除元素
            int ret = stack.pop();
            System.out.println(ret);//45

            // peek : 获取栈顶元素 但是不删除
            int ret2 = stack.peek();
            System.out.println(ret2);

            System.out.println(stack.isEmpty());

    }
}
